package LeetCode._02算法基础.day06广度深度优先搜索;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 16 - 9:33
 * @Description 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 * @Version 中等
 */
public class _200岛屿的数量 {
    static char[][] grid = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','1'}
    };
    @Test
    public void solve(){
        int res = numIslands(grid);
        System.out.println(res);
    }
    /*by me 深度优先搜索*/
    public int numIslands(char[][] grid) {
        //考虑非法情况
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int res = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                //是岛屿
                if(grid[i][j] == '1'){
                    search(grid, i, j, '1');
                    res++;
                }
            }
        }
        return res;
    }
    public void search(char[][] grid,int i, int j, char target){
        //出口
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != target){
            return;
        }
        //记录走过
        grid[i][j] = '2';
        //上
        search(grid, i - 1, j, target);
        //下
        search(grid, i + 1, j, target);
        //左
        search(grid, i , j -1, target);
        //右
        search(grid, i, j + 1, target);
    }
    /*官方思路 */
    //1.广度优先搜索
    public int numIslands1(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                //是岛屿
                if (grid[r][c] == '1') {
                    ++num_islands;
                    //标记走过
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    //当前位置加入队列
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        //上
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        //下
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        //左
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        //右
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }
        return num_islands;
    }

}
